#include "ai.h"
#include "ai_search.h"
#include "ai_search_mt.h"
#include "ai_reflex.h"
#include "ai_monte_carlo.h"
#include "ai_monte_carlo_mt.h"
#include "ai_replay.h"
#include "players.h"



int ai_support_computations::ai_test_fire_nobody( unsigned int x, unsigned int y, unsigned int tx, unsigned int ty, game_state* state )
{
	//starting position is water of wall
	if ( state->map->get( x, y ) >= 20000 )
		return -1;
	//destination position is water or wall
	if ( state->map->get( tx, ty ) >= 20000 )
		return -1;
	//starting position is destination position
	if ( ( x == tx ) && ( y == ty ) )
		return -1;
	//destination
	unsigned int d = ( unsigned int)abs( floor( sqrt( pow( ( float )( ( int )x - ( int )tx ), 2 ) + pow ( ( float )( ( int )y - ( int )ty ), 2 ) ) + 0.5 ) );
	double dx = abs( ( double )tx - ( double )x );
	double dy = abs( ( double )ty - ( double )y );
	//only orthogonal directions
	if ( dx == 0 )
	{
		dy = 1;
	}
	else if ( dy == 0 )
	{
		dx = 1;
	}
	//non ortogonal direction
	else
	{
		if ( dx > dy )
		{
			dy = dy / dx;
			dx = 1;
		}
		else
		{
			dx = dx / dy;
			dy = 1;	
		}
	}
	double cx = 0;
	double cy = 0;
	unsigned int fx = x;
	unsigned int fy = y;
	int px;
	int py;
	//direction of line
	if ( fx > tx )
		px = -1;
	else
		px = 1;
	if ( fy > ty )
		py = -1;
	else
		py = 1;
	bool move = false;
	//if compute exceeds sizes of map
	unsigned int test_d = 0;
	while ( !( fx == tx && fy == ty ) )
	{
		//out of map
		if ( test_d >= mapa::get_instance()->get_size_x() + mapa::get_instance()->get_size_y() )
			return -1;
		//wall
		if ( state->map->get( fx, fy ) > 20000 )
			return -1;
		if( !move )
		{
			cx += dx;
			cy += dy;
		}
		move = false;
		//movement
		if ( greater( cx, 0.5 ) )
		{
			--cx;
			fx += px;
			++test_d;
			move = true;
		}
		else if ( greater( cy, 0.5 ) )
		{
			--cy;
			fy += py;
			++test_d;
			move = true;
		}
	}
	return d;
};



int ai_support_computations::ai_test_move_nobody( unsigned int sx, unsigned int sy, unsigned int dx, unsigned int dy, game_state* state )
{
	//starting position is destination position
	if ( ( sx == dx ) && ( sy == dy ) )
		return 0;
	//starting position is water of wall
	if ( state->map->get( dx, dy ) >= 20000 )
		return -1;
	//destination position is water of wall
	if ( state->map->get( sx, sy ) >= 20000 )
		return -1;
	//array of distances to every place form [sx,sy]
	array2d< unsigned int > dist( mapa::get_instance()->get_size_x(), mapa::get_instance()->get_size_y() );
	for ( unsigned int i = 0; i < mapa::get_instance()->get_size_x(); ++i )
		for ( unsigned int j = 0; j < mapa::get_instance()->get_size_y(); ++j )
			dist.set( 30000, i, j );
	dist.set( 0, sx, sy );
	queue< pair< unsigned int, unsigned int > > fronta;
	fronta.push( make_pair< unsigned int, unsigned int >( sx, sy ) );
	unsigned int x;
	unsigned int y;	
	while ( !fronta.empty() )
	{
		x = fronta.front().first;
		y = fronta.front().second;
		fronta.pop();
		//move left
		if ( ( x > 0 ) && ( state->map->get( x - 1, y ) <= 1000 ) )
		{
			if ( dist.get( x - 1, y ) > dist.get( x, y ) + ( ( state->map->get( x - 1, y ) / 10 ) ) )
			{
				dist.set( dist.get( x, y ) + ( ( state->map->get( x - 1, y ) / 10 ) ), x - 1, y );
				fronta.push( make_pair< unsigned int, unsigned int >( x - 1, y ) );
			}		
		}
		//move right
		if ( ( x < mapa::get_instance()->get_size_x() - 1 ) && ( state->map->get( x + 1, y ) <= 1000 ) )
		{
			if ( dist.get( x + 1, y ) > dist.get( x, y ) + ( ( state->map->get( x + 1, y ) / 10 ) ) )
			{
				dist.set( dist.get( x, y ) + ( ( state->map->get( x + 1, y ) / 10 ) ), x + 1, y );
				fronta.push( make_pair< unsigned int, unsigned int >( x + 1, y ) );
			}
		}
		//move up
		if ( ( y > 0 ) && ( state->map->get( x, y - 1 ) <= 1000 ) )
		{
			if ( dist.get( x, y - 1 ) > dist.get( x, y ) + ( ( state->map->get( x, y - 1 ) / 10 ) ) )
			{
				dist.set( dist.get( x, y ) + ( ( state->map->get( x, y - 1 ) / 10 ) ), x, y - 1 );
				fronta.push( make_pair< unsigned int, unsigned int >( x, y - 1 ) );
			}
		}
		//move down
		if ( ( y < mapa::get_instance()->get_size_y() - 1 ) && ( state->map->get( x, y + 1 ) <= 1000 ) )
		{
			if ( dist.get( x, y + 1 ) > dist.get( x, y ) + ( ( state->map->get( x, y + 1 ) / 10 ) ) )
			{
				dist.set( dist.get( x, y ) + ( ( state->map->get( x, y + 1 ) / 10 ) ), x, y + 1 );
				fronta.push( make_pair< unsigned int, unsigned int >( x, y + 1 ) );
			}
		}
	}
	//destination unreachable
	if ( dist.get( dx, dy ) >= 30000 )
		return -1;
	else
	//destination reachable
		return ( dist.get( dx, dy ) );
};



int ai_support_computations::ai_test_fire( unsigned int x, unsigned int y, unsigned int tx, unsigned int ty, game_state* state )
{
	//starting position is water of wall
	if ( state->map->get( x, y ) >= 20000 )
		return -1;
	//destination position is water of wall
	if ( state->map->get( tx, ty ) >= 20000 )
		return -1;
	//starting position is destination position
	if ( ( x == tx ) && ( y == ty ) )
		return -1;
	//destination
	unsigned int d = ( unsigned int)abs( floor( sqrt( pow( ( float )( ( int )x - ( int )tx ), 2 ) + pow ( ( float )( ( int )y - ( int )ty ), 2 ) ) + 0.5 ) );
	double dx = abs( ( double )tx - ( double )x );
	double dy = abs( ( double )ty - ( double )y );
	//only ortogonal directions
	if ( dx == 0 )
	{
		dy = 1;
	}
	else if ( dy == 0 )
	{
		dx = 1;
	}
	//non ortogonal direction
	else
	{
		if(dx > dy)
		{
			dy = dy / dx;
			dx = 1;
		}
		else
		{
			dx = dx / dy;
			dy = 1;	
		}
	}
	double cx = 0;
	double cy = 0;
	unsigned int fx = x;
	unsigned int fy = y;
	int px;
	int py;
	//direction of line
	if ( fx > tx )
		px = -1;
	else
		px = 1;
	if( fy > ty )
		py = -1;
	else
		py = 1;
	bool move = false;
	//if compute exceeds sizes of map
	unsigned int test_d = 0;
	while ( !( fx == tx && fy == ty ) )
	{
		//out of map
		if ( test_d >= mapa::get_instance()->get_size_x() + mapa::get_instance()->get_size_y() )
			return -1;
		//wall
		if ( ( state->map->get( fx, fy ) > 20000 ) )
			return -1;
		//unit on path
		if ( ( ( dynamic_cast< unit* >( state->objects->get( fx, fy ) ) != 0 ) && ( ( ( fx != tx ) || ( fy != ty ) ) && ( ( fx != x ) || ( fy != y ) ) ) ) )
			return -1;
		if( !move )
		{
			cx += dx;
			cy += dy;
		}
		move = false;
		//movement
		if ( greater( cx, 0.5 ) )
		{
			--cx;
			fx += px;
			++test_d;
			move = true;
		}
		else if ( greater( cy, 0.5 ) )
		{
			--cy;
			fy += py;
			++test_d;
			move = true;
		}
	}
	return d;
}



int ai_support_computations::ai_test_move( unsigned int sx, unsigned int sy, unsigned int dx, int unsigned dy, game_state* state )
{
	//starting position is destination position
	if ( ( sx == dx ) && ( sy == dy ) )
		return 0;
	//destination position is water of wall or unit
	if ( ( state->map->get( dx, dy ) >= 20000 ) || ( ( dynamic_cast< unit* >( state->objects->get( dx, dy ) ) ) != 0 ) )
		return -1;
	//starting position is water of wall
	if ( state->map->get( sx, sy ) >= 20000 )
		return -1;
	//array of distances to every place form [sx,sy]
	array2d< unsigned int > dist( mapa::get_instance()->get_size_x(), mapa::get_instance()->get_size_y() );
	for ( unsigned int i = 0; i < mapa::get_instance()->get_size_x(); ++i )
		for ( unsigned int j = 0; j < mapa::get_instance()->get_size_y(); ++j )
			dist.set( 30000, i, j );
	dist.set( 0, sx, sy );
	queue< pair< unsigned int, unsigned int > > fronta;
	fronta.push( make_pair< unsigned int, unsigned int >( sx, sy ) );
	unsigned int x;
	unsigned int y;	
	while ( !fronta.empty() )
	{
		x = fronta.front().first;
		y = fronta.front().second;
		fronta.pop();
		//move left
		if ( ( x > 0 ) && ( state->map->get( x - 1, y ) <= 1000 ) && ( ( dynamic_cast< unit* >( state->objects->get( x - 1, y ) ) ) == 0 ) )
		{
			if ( dist.get( x - 1, y ) > dist.get( x, y ) + ( ( state->map->get( x - 1, y ) / 10 ) ) )
			{
				dist.set( dist.get( x, y ) + ( ( state->map->get( x - 1, y ) / 10 ) ), x - 1, y );
				fronta.push( make_pair< unsigned int, unsigned int >( x - 1, y ) );
			}		
		}
		//move right
		if ( ( x < mapa::get_instance()->get_size_x() - 1 ) && ( state->map->get( x + 1, y ) <= 1000 ) && ( ( dynamic_cast< unit* >( state->objects->get( x + 1, y ) ) ) == 0 ) )
		{
			if ( dist.get( x + 1, y ) > dist.get( x, y ) + ( ( state->map->get( x + 1, y ) / 10 ) ) )
			{
				dist.set( dist.get( x, y ) + ( ( state->map->get( x + 1, y ) / 10 ) ), x + 1, y );
				fronta.push( make_pair< unsigned int, unsigned int >( x + 1, y ) );
			}
		}
		//move up
		if ( ( y > 0 ) && ( state->map->get( x, y - 1 ) <= 1000 ) && ( ( dynamic_cast< unit* >( state->objects->get( x, y - 1 ) ) ) == 0 ) )
		{
			if ( dist.get( x, y - 1 ) > dist.get( x, y ) + ( ( state->map->get( x, y - 1 ) / 10 ) ) )
			{
				dist.set( dist.get( x, y ) + ( ( state->map->get( x, y - 1 ) / 10 ) ), x, y - 1 );
				fronta.push( make_pair< unsigned int, unsigned int >( x, y - 1 ) );
			}
		}
		//move down
		if ( ( y < mapa::get_instance()->get_size_y() - 1 ) && ( state->map->get( x, y + 1 ) <= 1000 ) && ( ( dynamic_cast< unit* >( state->objects->get( x, y + 1 ) ) ) == 0 ) )
		{
			if ( dist.get( x, y + 1 ) > dist.get( x, y ) + ( ( state->map->get( x, y + 1 ) / 10 ) ) )
			{
				dist.set( dist.get( x, y ) + ( ( state->map->get( x, y + 1 ) / 10 ) ), x, y + 1 );
				fronta.push( make_pair< unsigned int, unsigned int >( x, y + 1 ) );
			}
		}
	}
	//destination unreachable
	if ( dist.get( dx, dy ) >= 30000 )
		return -1;
	else
	//destination reachable
		return ( dist.get( dx, dy ) );
};



int ai_support_computations::ai_test_buy( unsigned int pl, unit* u, unsigned int x, unsigned int y, game_state* state )
{
	if ( dynamic_cast< object* >( state->objects->get( x, y ) ) != 0 )
		return -1;
	if ( state->map->get( x, y ) >= 20000 )
		return -1;
	if ( state->map->get( x, y ) % 10 != ( pl + 1 ) )
		return -1;
	return u->get_price();
};



bool ai_support_computations::ai_move( unit* u, unsigned int x, unsigned int y, game_state* state )
{
	//distance
	int d = ai_test_move( u->get_x(), u->get_y(), x, y, state );
	//movement is possible
	if ( ( d != -1 ) && ( ( d * ( ( int )u->get_cost_move() ) ) <= u->get_player()->get_time() ) )
	{	
		u->get_player()->set_time( u->get_player()->get_time() - ( d * ( int )u->get_cost_move() ) );
		bonus* b = dynamic_cast< bonus* >( state->objects->get( x, y ) );
		//get bonus
		if ( b!= 0 )
		{
			b->effect( u );
			state->objects->set( 0, b->get_x(), b->get_y() );
			delete b;
		}
		state->objects->set( 0, u->get_x(), u->get_y() );
		u->set_pos( x, y );
		state->objects->set( u, x, y );
		return true;
	}
	else
	{
		return false;
	}
};



bool ai_support_computations::ai_fire( unit* u, unsigned int x, unsigned int y, game_state* state )
{
	//distance
	int d = ai_test_fire( u->get_x(), u->get_y(), x, y, state );
	//fire is possible
	if ( ( d != -1 ) && ( d <= ( int )u->get_range() ) && ( ( int )u->get_cost_fire() <= u->get_player()->get_time() ) )
	{
		unit* tu = dynamic_cast< unit* >( state->objects->get( x, y ) );
		//target present
		if ( tu != 0 )
		{
			if ( u->get_player() == tu->get_player() )
				return false;
			u->get_player()->set_time( u->get_player()->get_time() - ( int )u->get_cost_fire() );
			int x = ( int )u->get_weapon() - ( int )tu->get_shield();
			if ( x > 0 )
				tu->set_health( tu->get_health() - x );
			else
				tu->set_health( tu->get_health() - 1 );
			//target destroyed
			if ( tu->get_health() <= 0 )
			{
				player* tup = tu->get_player();
				state->objects->set( 0, tu->get_x(), tu->get_y() );
				for ( vector< unit* >::iterator it = tu->get_player()->units.begin(); it != tu->get_player()->units.end(); ++it )
				{
					if ( *it == tu )
					{
						tu->get_player()->units.erase( it );
						break;
					}
				}
				delete tu;
				if ( tup->units.empty() )
					tup->set_out();
			}
			return true;
		}
		else
		{
			return false;
		}

	}
	else
	{
		return false;
	}
};



bool ai_support_computations::ai_buy( unit* u, unsigned int x, unsigned int y, game_state* state )
{
	int p = ai_test_buy( state->current_player_id, u, x, y, state );
	if ( ( p != -1 ) && ( p <= state->plrs[ state->current_player_id ]->get_time() ) && ( state->plrs[ state->current_player_id ]->units.size() < parameters::get_instance()->game_parameters[ "MAX_UNITS" ] ) )
	{
		unit* nu = dynamic_cast< unit* >( u->clone() );
		state->plrs[ state->current_player_id ]->units.push_back( nu );
		nu->init( x, y, state->plrs[ state->current_player_id ], ( state->plrs[ state->current_player_id ]->units.size() + 1 ) );
		state->objects->set( nu, x, y );
		state->plrs[ state->current_player_id ]->set_time( state->plrs[ state->current_player_id ]->get_time() - nu->get_price() );
		return true;
	}
	else
	{
		return false;
	}
};



bool ai_support_computations::ai_sell( unsigned int n, game_state* state )
{
	if ( n < state->plrs[ state->current_player_id ]->units.size() )
	{
		vector< unit* >::iterator it = state->plrs[ state->current_player_id ]->units.begin() + n;
		unit* u = *it;
		state->objects->set( 0, u->get_x(), u->get_y() );
		state->plrs[ state->current_player_id ]->set_time( state->plrs[ state->current_player_id ]->get_time() + u->get_price() );
		delete u;
		state->plrs[ state->current_player_id ]->units.erase( state->plrs[ state->current_player_id ]->units.begin() + n );
		return true;
	}
	else
	{
		return false;
	}
};



void ai_support_computations::ai_next_turn( game_state* state )
{
	unsigned int current_player_id = state->current_player_id;
	//find next player
	for ( unsigned int i = 0; i < state->players_count; ++i )
	{
		++current_player_id;
		current_player_id = current_player_id % state->players_count;
		if ( state->plrs[ current_player_id ]->is_in_game() )
			break;
	}
	//set current player
	state->current_player_id = current_player_id;
	state->plrs[ current_player_id ]->set_time( parameters::get_instance()->game_parameters[ "START_TIME" ] );
};



void ai_support_computations::ai_end_buy( game_state* state )
{
	//TODO: all players finished buy?
	unsigned int current_player_id = state->current_player_id;
	//find next player
	for ( unsigned int i = 0; i < state->players_count; ++i )
	{
		++current_player_id;
		current_player_id = current_player_id % state->players_count;
		if ( state->plrs[ current_player_id ]->is_in_game() )
			break;
	}
	//set current player
	state->current_player_id = current_player_id;
	state->plrs[ current_player_id ]->set_time( parameters::get_instance()->game_parameters[ "START_MONEY" ] );
};



bool ai_support_computations::apply_command( game_state* state, const string& cmd )
{
	istringstream sstr( cmd );
	string c;
	unsigned int x;
	unsigned int y;
	unsigned int u;
	sstr >> c;

	if ( sstr.fail() )
	{
		return false;
	}
	//SEL U
	//sell unit with id u
	else if ( c == "SEL" )
	{
		sstr >> u;
		if ( ai_support_computations::ai_sell( u, state ) )
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	//ATT U X Y
	//attack with unit u to [x,y]
	else if ( c == "ATT" )
	{
		sstr >> u;
		sstr >> x;
		sstr >> y;
		if ( ai_support_computations::ai_fire( state->plrs[ state->current_player_id ]->units[ u ], x, y, state ) )
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	//MOV U X Y
	//move with unit u to [x,y]
	else if ( c == "MOV" )
	{
		sstr >> u;
		sstr >> x;
		sstr >> y;
		if ( ai_support_computations::ai_move( state->plrs[ state->current_player_id ]->units[ u ], x, y, state ) )
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	//NXT
	//next turn
	else if ( c == "NXT" )
	{
		ai_support_computations::ai_next_turn( state );
		return true;
	}
	//END
	//end buy
	else if ( c == "END" )
	{
		ai_support_computations::ai_end_buy( state );
		return true;
	}
	//BUY U X Y
	//buy unit u to [x,y]
	else if ( c == "BUY" )
	{
		sstr >> u;
		sstr >> x;
		sstr >> y;
		if ( ai_support_computations::ai_buy( prototypes::get_instance()->unit_pos_iterator( u )->second, x, y, state ) )
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	//unknown command
	else
		return false;
};



array2d< unsigned int >* ai_support_computations::map_places_estimate( game_state* state )
{
	array2d< unsigned int >* estimated_places = new array2d< unsigned int >( mapa::get_instance()->get_size_x(), mapa::get_instance()->get_size_y() );

	for ( unsigned int i = 0; i < mapa::get_instance()->get_size_x(); ++i )
		for ( unsigned int j = 0; j < mapa::get_instance()->get_size_y(); ++j )
			estimated_places->set( 0, i, j );
	
	int d;
	//for search only of possible square
	unsigned int search_top;
	unsigned int search_left;
	unsigned int search_bottom;
	unsigned int search_right;
	for ( unsigned int x = 0; x < mapa::get_instance()->get_size_x(); ++x )
		for ( unsigned int y = 0; y < mapa::get_instance()->get_size_y(); ++y )
		{
			//wall or water
			if ( state->map->get( x, y ) >= 20000 )
				continue;
			//unreachable place
			if ( state->reachable_places->get( x, y ) == false )
				continue;
			//compute search ranges (square where to search for possibilities)
			search_top = ( ( ( int )y - ( int )parameters::get_instance()->ai_parameters[ "GENERAL" ][ "test_range" ] ) > 0 ) ? ( unsigned int )( y - parameters::get_instance()->ai_parameters[ "GENERAL" ][ "test_range" ] ) : 0;
			search_left = ( ( ( int )x - ( int )parameters::get_instance()->ai_parameters[ "GENERAL" ][ "test_range" ] ) > 0 ) ? ( unsigned int )( x - parameters::get_instance()->ai_parameters[ "GENERAL" ][ "test_range" ] ) : 0;
			search_bottom = ( ( y + parameters::get_instance()->ai_parameters[ "GENERAL" ][ "test_range" ] ) < mapa::get_instance()->get_size_y() ) ? ( unsigned int )( y + parameters::get_instance()->ai_parameters[ "GENERAL" ][ "test_range" ] ) : ( mapa::get_instance()->get_size_y() - 1 );
			search_right = ( ( x + parameters::get_instance()->ai_parameters[ "GENERAL" ][ "test_range" ] ) < mapa::get_instance()->get_size_x() ) ? ( unsigned int )( x + parameters::get_instance()->ai_parameters[ "GENERAL" ][ "test_range" ] ) : ( mapa::get_instance()->get_size_x() - 1 );
			for ( unsigned int tx = search_left; tx <= search_right; ++tx )
				for ( unsigned int ty = search_top; ty <= search_bottom; ++ty )
				{
					//wall or water
					if ( state->map->get( tx, ty ) >= 20000 )
						continue;
					//unreachable place
					if ( state->reachable_places->get( x, y ) == false )
						continue;
					//distance
					d = ai_test_fire_nobody( x, y, tx, ty, state);
					if ( ( d != -1 ) && ( d <= parameters::get_instance()->ai_parameters[ "GENERAL" ][ "test_range" ] ) )
					{
						estimated_places->set( estimated_places->get( tx, ty ) + 1, tx, ty );
					}
				}
		}

	return estimated_places;
};



array2d< bool >* ai_support_computations::map_places_reachable( game_state* state )
{
	array2d< bool >* reachable_places = new array2d< bool >( mapa::get_instance()->get_size_x(), mapa::get_instance()->get_size_y() );
	queue< pair< unsigned int, unsigned int > > fronta;

	for ( unsigned int i = 0; i < mapa::get_instance()->get_size_x(); ++i )
		for ( unsigned int j = 0; j < mapa::get_instance()->get_size_y(); ++j )
			reachable_places->set( false, i, j );

	//possible starting palces (where units are be bought)
	for ( unsigned int i = 0; i < mapa::get_instance()->get_size_x(); ++i )
		for ( unsigned int j = 0; j < mapa::get_instance()->get_size_y(); ++j )
			if ( ( state->map->get( i, j ) % 10 ) != 0 )
				fronta.push( make_pair< unsigned int, unsigned int >( i, j ) );

	unsigned int x;
	unsigned int y;	

	while ( !fronta.empty() )
	{
		x = fronta.front().first;
		y = fronta.front().second;
		fronta.pop();
		if ( reachable_places->get( x, y ) == false )
		{
			reachable_places->set( true, x, y );
			//move left
			if ( ( x > 0 ) && ( state->map->get( x - 1, y ) <= 1000 ) && ( reachable_places->get( x - 1, y ) == false ) )
				fronta.push( make_pair< unsigned int, unsigned int >( x-1, y ) );	
			//move right
			if ( ( x < mapa::get_instance()->get_size_x() - 1 ) && ( state->map->get( x + 1, y ) <= 1000 ) && ( reachable_places->get( x + 1, y ) == false ) )
				fronta.push( make_pair< unsigned int, unsigned int >( x + 1, y ) );
			//move up
			if ( (y > 0 ) && ( state->map->get( x, y - 1 ) <= 1000 ) && ( reachable_places->get( x, y - 1 ) == false ) )
				fronta.push( make_pair< unsigned int, unsigned int >( x, y - 1 ) );
			//move down
			if ( ( y < mapa::get_instance()->get_size_y() - 1 ) && ( state->map->get( x, y + 1 ) <= 1000 ) && ( reachable_places->get( x, y + 1 ) == false ) )
				fronta.push( make_pair< unsigned int, unsigned int >( x, y + 1 ) );
		}
	}

	return reachable_places;
};



array2d< unsigned int >* ai_support_computations::map_places_dangerous( game_state* state )
{
	array2d< unsigned int >* dangerous_places = new array2d< unsigned int >( mapa::get_instance()->get_size_x(), mapa::get_instance()->get_size_y() );;

	for ( unsigned int i = 0; i < mapa::get_instance()->get_size_x(); ++i )
		for( unsigned int j = 0; j < mapa::get_instance()->get_size_y(); ++j )
			dangerous_places->set( 0, i, j );

	int d;
	//for search only of possible square
	unsigned int search_top;
	unsigned int search_left;
	unsigned int search_bottom;
	unsigned int search_right;
	unit* test_u;
	for ( unsigned int cpl = 0; cpl < state->players_count; ++cpl )
	{
		if ( state->plrs[ cpl ]->get_id() == ( int )state->current_player_id )
			continue;
		for ( unsigned int cun = 0; cun < state->plrs[ cpl ]->units.size(); ++cun )
		{
			test_u = state->plrs[ cpl ]->units[ cun ];
			//compute search ranges (square where to search for possibilities)
			search_top = ( ( ( int )test_u->get_y() - ( int )state->plrs[ cpl ]->units[ cun ]->get_range() ) > 0 ) ? ( test_u->get_y() - state->plrs[ cpl ]->units[ cun ]->get_range() ) : 0;
			search_left = ( ( ( int )test_u->get_x() - ( int )state->plrs[ cpl ]->units[ cun ]->get_range() ) > 0 ) ? ( test_u->get_x() - state->plrs[ cpl ]->units[ cun ]->get_range() ) : 0;
			search_bottom = ( ( test_u->get_y() + state->plrs[ cpl ]->units[ cun ]->get_range() ) < mapa::get_instance()->get_size_y() ) ? ( test_u->get_y() + state->plrs[ cpl ]->units[ cun ]->get_range() ) : ( mapa::get_instance()->get_size_y() - 1 );
			search_right = ( ( test_u->get_x() + state->plrs[ cpl ]->units[ cun ]->get_range() ) < mapa::get_instance()->get_size_x() ) ? ( test_u->get_x() + state->plrs[ cpl ]->units[ cun ]->get_range() ) : ( mapa::get_instance()->get_size_x() - 1 );
			for ( unsigned int tx = search_left; tx <= search_right; ++tx )
				for ( unsigned int ty = search_top; ty <= search_bottom; ++ty )
				{
					//water or wall
					if ( state->map->get( tx, ty ) >= 20000 )
						continue;
					//distance
					d = ai_test_fire( state->plrs[ cpl ]->units[ cun ]->get_x(), state->plrs[ cpl ]->units[ cun ]->get_y(), tx, ty, state );
					if ( ( d != -1 ) && ( d <= ( int )state->plrs[ cpl ]->units[ cun ]->get_range() ) )
						if ( dangerous_places->get( tx, ty ) < state->plrs[ cpl ]->units[ cun ]->get_weapon() )
							dangerous_places->set( state->plrs[ cpl ]->units[ cun ]->get_weapon(), tx, ty );
				}
		}
	}

	return dangerous_places;
};



array2d< unsigned int >* ai_support_computations::map_places_dangerous_nobody( game_state* state )
{
	array2d< unsigned int >* dangerous_places_nobody = new array2d< unsigned int >( mapa::get_instance()->get_size_x(), mapa::get_instance()->get_size_y() );;

	for ( unsigned int i = 0; i < mapa::get_instance()->get_size_x(); ++i )
		for( unsigned int j = 0; j < mapa::get_instance()->get_size_y(); ++j )
			dangerous_places_nobody->set( 0, i, j );

	int d;
	//for search only of possible square
	unsigned int search_top;
	unsigned int search_left;
	unsigned int search_bottom;
	unsigned int search_right;
	unit* test_u;
	for ( unsigned int cpl = 0; cpl < state->players_count; ++cpl )
	{
		if ( state->plrs[ cpl ]->get_id() == ( int )state->current_player_id )
			continue;
		for ( unsigned int cun = 0; cun < state->plrs[ cpl ]->units.size(); ++cun )
		{
			test_u = state->plrs[ cpl ]->units[ cun ];
			//compute search ranges (square where to search for possibilities)
			search_top = ( ( ( int )test_u->get_y() - ( int )state->plrs[ cpl ]->units[ cun ]->get_range() ) > 0 ) ? ( test_u->get_y() - state->plrs[ cpl ]->units[ cun ]->get_range() ) : 0;
			search_left = ( ( ( int )test_u->get_x() - ( int )state->plrs[ cpl ]->units[ cun ]->get_range() ) > 0 ) ? ( test_u->get_x() - state->plrs[ cpl ]->units[ cun ]->get_range() ) : 0;
			search_bottom = ( ( test_u->get_y() + state->plrs[ cpl ]->units[ cun ]->get_range() ) < mapa::get_instance()->get_size_y() ) ? ( test_u->get_y() + state->plrs[ cpl ]->units[ cun ]->get_range() ) : ( mapa::get_instance()->get_size_y() - 1 );
			search_right = ( ( test_u->get_x() + state->plrs[ cpl ]->units[ cun ]->get_range() ) < mapa::get_instance()->get_size_x() ) ? ( test_u->get_x() + state->plrs[ cpl ]->units[ cun ]->get_range() ) : ( mapa::get_instance()->get_size_x() - 1 );
			for ( unsigned int tx = search_left; tx <= search_right; ++tx )
				for ( unsigned int ty = search_top; ty <= search_bottom; ++ty )
				{
					//water or wall
					if ( state->map->get( tx, ty ) >= 20000 )
						continue;
					//distance
					d = ai_test_fire_nobody( state->plrs[ cpl ]->units[ cun ]->get_x(), state->plrs[ cpl ]->units[ cun ]->get_y(), tx, ty, state );
					if ( ( d != -1 ) && ( d <= ( int )state->plrs[ cpl ]->units[ cun ]->get_range() ) )
						if ( dangerous_places_nobody->get( tx, ty ) < state->plrs[ cpl ]->units[ cun ]->get_weapon() )
							dangerous_places_nobody->set( state->plrs[ cpl ]->units[ cun ]->get_weapon(), tx, ty );
				}
		}
	}

	return dangerous_places_nobody;
};



array2d< unsigned int >* ai_support_computations::map_places_attackable( game_state* state )
{
	array2d< unsigned int >* attackable_places = new array2d< unsigned int >( mapa::get_instance()->get_size_x(), mapa::get_instance()->get_size_y() );

	for ( unsigned int i = 0; i < mapa::get_instance()->get_size_x(); ++i )
		for( unsigned int j = 0; j < mapa::get_instance()->get_size_y(); ++j )
			attackable_places->set( 0, i, j );

	int d;
	//for search only of possible square
	unsigned int search_top;
	unsigned int search_left;
	unsigned int search_bottom;
	unsigned int search_right;
	unit* test_u;
	for ( unsigned int cun = 0; cun < state->plrs[ state->current_player_id ]->units.size(); ++cun )
	{
		test_u = state->plrs[ state->current_player_id ]->units[ cun ];
		//compute search ranges (square where to search for possibilities)
		search_top = ( ( ( int )test_u->get_y() - ( int )state->plrs[ state->current_player_id ]->units[ cun ]->get_range() ) > 0 ) ? ( test_u->get_y() - state->plrs[ state->current_player_id ]->units[ cun ]->get_range() ) : 0;
		search_left = ( ( ( int )test_u->get_x() - ( int )state->plrs[ state->current_player_id ]->units[ cun ]->get_range() ) > 0 ) ? ( test_u->get_x() - state->plrs[ state->current_player_id ]->units[ cun ]->get_range() ) : 0;
		search_bottom = ( ( test_u->get_y() + state->plrs[ state->current_player_id ]->units[ cun ]->get_range() ) < mapa::get_instance()->get_size_y() ) ? ( test_u->get_y() + state->plrs[ state->current_player_id ]->units[ cun ]->get_range() ) : ( mapa::get_instance()->get_size_y() - 1 );
		search_right = ( ( test_u->get_x() + state->plrs[ state->current_player_id ]->units[ cun ]->get_range() ) < mapa::get_instance()->get_size_x() ) ? ( test_u->get_x() + state->plrs[ state->current_player_id ]->units[ cun ]->get_range() ) : ( mapa::get_instance()->get_size_x() - 1 );
		for ( unsigned int tx = search_left; tx <= search_right; ++tx )
			for ( unsigned int ty = search_top; ty <= search_bottom; ++ty )
			{
				//water or wall
				if ( state->map->get( tx, ty ) >= 20000 )
					continue;
				//distance
				d = ai_test_fire( state->plrs[ state->current_player_id ]->units[ cun ]->get_x(), state->plrs[ state->current_player_id ]->units[ cun ]->get_y(), tx, ty, state );
				if ( ( d != -1 ) && ( d <= ( int )state->plrs[ state->current_player_id ]->units[ cun ]->get_range() ) )
					if ( attackable_places->get( tx, ty ) < state->plrs[ state->current_player_id ]->units[ cun ]->get_weapon() )
						attackable_places->set( state->plrs[ state->current_player_id ]->units[ cun ]->get_weapon(), tx, ty );
			}
	}

	return attackable_places;
};



vector< array2d< unsigned int >* >* ai_support_computations::map_places_range( game_state* state )
{
	vector< array2d< unsigned int >* >* range_places = new vector< array2d< unsigned int >* >( state->plrs[ state->current_player_id ]->units.size() );
	
	for ( vector< array2d< unsigned int >* >::iterator it = range_places->begin(); it != range_places->end(); ++it )
	{
		*it = new array2d< unsigned int >( mapa::get_instance()->get_size_x(), mapa::get_instance()->get_size_y() );
		for ( unsigned int i = 0; i < mapa::get_instance()->get_size_x(); ++i )
			for( unsigned int j = 0; j < mapa::get_instance()->get_size_y(); ++j )
				( *it )->set( 0, i, j );
	}
	
	unsigned int tx;
	unsigned int ty;
	for ( unsigned int ax = 0; ax < mapa::get_instance()->get_size_x(); ++ax )
		for ( unsigned int ay = 0; ay < mapa::get_instance()->get_size_y(); ++ay )
		{
			for ( unsigned int apl = 0; apl < state->players_count; ++apl )
			{
				if ( state->plrs[ apl ]->get_id() == ( int )state->current_player_id )
					continue;
				for ( unsigned int aun = 0; aun < state->plrs[ apl ]->units.size(); ++aun )
				{
					tx = state->plrs[ apl ]->units[ aun ]->get_x();
					ty = state->plrs[ apl ]->units[ aun ]->get_y();
					int test_range = ai_support_computations::ai_test_fire( ax, ay, tx, ty, state );
					if ( test_range != -1 )
					{
						for ( unsigned int cun = 0; cun < state->plrs[ state->current_player_id ]->units.size(); ++cun )
						{
							if ( test_range <= ( int )state->plrs[ state->current_player_id ]->units[ cun ]->get_range() )
								( *range_places )[ cun ]->set( ( *range_places )[ cun ]->get( ax, ay ) + 1, ax, ay );
						}
					}
				}
			}
		}

	return range_places;
};



double ai_support_computations::game_state_estimate( game_state* state )
{
	//vector of mean power for each army
	vector< double > army_power( state->players_count );
	//vector of mean weapon strength
	vector< double > weapons_strength( state->players_count );
	//mean opponents weapon
	vector< double > mean_opponents_weapon( state->players_count );
	//sum opponents power
	double sum_opponents_power;
	//remaining turns assumption
	double remaining_turns;
	//expected harm caused by army
	double expected_harm;
	//army endurance
	vector< double > army_endurance( state->players_count );
	//sum opponents endurance
	double sum_opponents_endurance;
	//number of alive players in game
	unsigned int players_in_game;
	//state balance not considering position
	double army_balance = 0;

	parameters* param = parameters::get_instance();

	if ( param->ai_parameters[ "GENERAL" ][ "army_balance_coef" ] != 0 )
	{
		//army_power, weapons_strength and players_in_game calculation
		players_in_game = 0;
		for ( unsigned int p = 0; p < state->players_count; ++p )
		{
			if ( state->plrs[ p ]->is_in_game() )
				++players_in_game;

			double power = 0;
			double weapons = 0;
			for ( vector< unit* >::iterator it = state->plrs[ p ]->units.begin(); it != state->plrs[ p ]->units.end(); ++it )
			{
				power += parameters::get_instance()->game_parameters[ "START_TIME" ] / ( *it )->get_cost_fire() * ( *it )->get_weapon();
				weapons += ( *it )->get_weapon();
			}
			if ( state->plrs[ p ]->units.empty() )
			{
				army_power[ p ] = 0;
				weapons_strength[ p ] = 0;
			}
			else
			{
				army_power[ p ] = power / state->plrs[ p ]->units.size();
				weapons_strength[ p ] = weapons / state->plrs[ p ]->units.size();
			}
		}

		//mean_opponents_weapon calculation
		for ( unsigned int p = 0; p < state->players_count; ++p )
		{
			double opponents_weapon = 0;
			for ( unsigned int op = 0; op < state->players_count; ++op )
			{
				if ( op == p )
					continue;
				opponents_weapon += weapons_strength[ op ];
			}
			if ( players_in_game == 1 )
			{
				mean_opponents_weapon[ p ] = 0;
			}
			else
			{
				mean_opponents_weapon[ p ] = opponents_weapon / ( players_in_game - 1 );
			}
		}

		//sum_opponents_power calculation
		sum_opponents_power = 0;
		for ( unsigned int op = 0; op < state->players_count; ++op )
		{
			if ( op == state->current_player_id )
				continue;
			sum_opponents_power += army_power[ op ];
		}

		//army_endurance calculation
		for ( unsigned int p = 0; p < state->players_count; ++p )
		{		
			double endurance = 0;
			double opp_harm;
			for ( vector< unit* >::iterator it = state->plrs[ p ]->units.begin(); it != state->plrs[ p ]->units.end(); ++it )
			{
				opp_harm = mean_opponents_weapon[ p ] - ( int )( *it )->get_shield() < 1 ? 1 : mean_opponents_weapon[ p ] - ( int )( *it )->get_shield();
				endurance += ( *it )->get_health() + ( *it )->get_health() / opp_harm * ( *it )->get_shield();
			}
			army_endurance[ p ] = endurance;
		}

		//remaining_turns calculation
		if ( players_in_game == 1 )
		{
			remaining_turns = 1e50; //HACK
		}
		else
		{
			remaining_turns = army_endurance[ state->current_player_id ] / ( sum_opponents_power / ( players_in_game - 1 ) );
		}
		
		//expected_harm calculation
		expected_harm = remaining_turns * army_power[ state->current_player_id ];
		
		//sum_opponents_endurance calculation
		sum_opponents_endurance = 0;
		for ( unsigned int op = 0; op < state->players_count; ++op )
		{
			if ( op == state->current_player_id )
				continue;
			sum_opponents_endurance += army_endurance[ op ];
		}
		if ( players_in_game == 1 )
		{
			army_balance = expected_harm;
		}
		else
		{
			army_balance = expected_harm - sum_opponents_endurance / ( players_in_game - 1 );
		}
	}

	//harm, that can opponent cause to current players units
	double army_vulnerability = 0;
	//distance of current players army from places, from where he can attack
	double army_distances = 0;
	//number in current players units in danger;
	unsigned int units_in_danger = 0;

	for ( vector< unit* >::iterator it = state->plrs[ state->current_player_id ]->units.begin(); it != state->plrs[ state->current_player_id ]->units.end(); ++it )
	{
		bool endangered = false;
		if ( param->ai_parameters[ "GENERAL" ][ "army_vulnerability_coef" ] != 0 )
		{
			if ( state->dangerous_places->get( ( *it )->get_x(), ( *it )->get_y() ) > 0 )
			{
				endangered = true;
				army_vulnerability += ( int )state->dangerous_places->get( ( *it )->get_x(), ( *it )->get_y() ) - ( int )( *it )->get_shield() < 1 ? 1 : ( int )state->dangerous_places->get( ( *it )->get_x(), ( *it )->get_y() ) - ( int )( *it )->get_shield();
			}
		}

		if ( param->ai_parameters[ "GENERAL" ][ "army_distances_coef" ] != 0 )
		{
			int distance = mapa::get_instance()->get_size_x() * mapa::get_instance()->get_size_y();

			for ( unsigned int x = 0; x < mapa::get_instance()->get_size_x(); ++x )
				for ( unsigned int y = 0; y < mapa::get_instance()->get_size_y(); ++y )
				{
					if ( ( *state->range_places )[ ( *it )->get_id() ]->get( x, y ) > 0 )
					{		
						int d = ai_support_computations::ai_test_move_nobody( ( *it )->get_x(), ( *it )->get_y(), x, y, state );
						if ( ( d != -1 ) && ( d < distance ) )
							distance = d;
					}
				}

			army_distances += distance * ( *it )->get_cost_move();
		}

		if ( endangered )
			++units_in_danger;
	}

	if ( state->plrs[ state->current_player_id ]->units.empty() )
	{
		army_vulnerability = 0;
		army_distances = 0;
	}
	else
	{
		army_distances /= state->plrs[ state->current_player_id ]->units.size();
		if ( units_in_danger == 0 )
			army_vulnerability = 0;
		else
			army_vulnerability /= ( state->plrs[ state->current_player_id ]->units.size() * units_in_danger );
	}

	return ( army_balance * param->ai_parameters[ "GENERAL" ][ "army_balance_coef" ] - army_vulnerability * param->ai_parameters[ "GENERAL" ][ "army_vulnerability_coef" ] - army_distances * param->ai_parameters[ "GENERAL" ][ "army_distances_coef" ] );
};



game_state::game_state( unsigned int pl_c, unsigned int c_pl_id, player** pl, array2d< object* >* obj, array2d< unsigned int >* mp, double sc, array2d< unsigned int >* ep, array2d< bool >* rp, array2d< unsigned int >* dp, array2d< unsigned int >* dpn, array2d< unsigned int >* ap, vector< array2d< unsigned int >* >* rgp )
{
	plrs = new player*[ parameters::get_instance()->game_parameters[ "MAX_PL" ] ];
	score = sc;
	map = mp;

	//cloning of objects
	objects = new array2d< object* >( mapa::get_instance()->get_size_x(), mapa::get_instance()->get_size_y() );
	for ( unsigned int i = 0; i < mapa::get_instance()->get_size_x(); ++i )
		for ( unsigned int j = 0; j < mapa::get_instance()->get_size_y(); ++j )
			objects->set( 0, i, j );

	current_player_id = c_pl_id;

	//cloning of players
	players_count = pl_c;
	for ( unsigned int i = 0; i < pl_c; ++i )
		plrs[ i ] = pl[ i ]->clone();

	//setting units to objects map
	for ( unsigned int i = 0; i < players_count; ++i )
		for( unsigned int j = 0; j < plrs[ i ]->units.size(); ++j )
		{
			objects->set( plrs[ i ]->units[ j ], plrs[ i ]->units[ j ]->get_x(), plrs[ i ]->units[ j ]->get_y() );
		}

	//cloning of other objects than units
	for ( unsigned int i = 0; i < mapa::get_instance()->get_size_x(); ++i )
		for ( unsigned int j = 0; j < mapa::get_instance()->get_size_y(); ++j )
		{
			if ( ( obj->get( i, j ) != 0 ) && ( ( dynamic_cast< unit* >( obj->get( i, j ) ) ) == 0 ) )
				objects->set( obj->get( i, j )->clone(), i, j );
		}

	estimated_places = ep;
	reachable_places = rp;
	dangerous_places = dp;
	dangerous_places_nobody = dpn;
	attackable_places = ap;
	range_places = rgp;
};



game_state::~game_state()
{
	for( unsigned int i = 0; i < players_count; ++i )
		delete plrs[ i ];
	delete [] plrs;
	delete map;
	delete objects;
	if ( estimated_places != 0 )
		delete estimated_places;
	if ( reachable_places != 0 )
		delete reachable_places;
	if ( dangerous_places != 0 )
		delete dangerous_places;
	if ( dangerous_places_nobody != 0 )
		delete dangerous_places_nobody;
	if ( attackable_places != 0 )
		delete attackable_places;
	if ( range_places != 0 )
	{
		for ( vector< array2d< unsigned int >* >::iterator it = range_places->begin(); it != range_places->end(); ++it )
			delete *it;
		delete range_places;
	}
};



bool game_state::equals( game_state* s )
{
	if ( s == 0 )
		return false;
	if ( !( ( players_count == s->players_count ) &&
		 ( current_player_id == s->current_player_id ) ) )
	{
		return false;
	}
	for ( unsigned int p = 0; p < players_count; ++p )
	{
		if ( !( plrs[ p ]->equals( s->plrs[ p ] ) ) )
			return false;
	}
	for ( unsigned int x = 0; x < mapa::get_instance()->get_size_x(); ++x )
		for ( unsigned int y = 0; y < mapa::get_instance()->get_size_y(); ++y )
		{
			//testing object exists
			if ( objects->get( x, y ) != 0 )
			{
				//but is not equal to tested or tested does not exist
				if ( !( objects->get( x, y )->equals( s->objects->get( x, y ) ) ) )
					return false;
			}
			else
			//no testing object on this position
			{
				//but tested object exists
				if ( s->objects->get( x, y ) != 0 )
					return false;
			}
		}
	return true;
};



game_state* game_state::clone() const
{
	game_state* gs = new game_state( players_count, current_player_id, plrs, objects, new array2d< unsigned int >( *map ), score );
	if ( estimated_places != 0 )
		gs->estimated_places = new array2d< unsigned int >( *estimated_places );
	if ( reachable_places != 0 )
		gs->reachable_places = new array2d< bool >( *reachable_places );
	if ( dangerous_places != 0 )
		gs->dangerous_places = new array2d< unsigned int >( *dangerous_places );
	if ( dangerous_places_nobody != 0 )
		gs->dangerous_places_nobody = new array2d< unsigned int >( *dangerous_places_nobody );
	if ( attackable_places != 0 )
		gs->attackable_places = new array2d< unsigned int >( *attackable_places );
	if ( range_places != 0 )
	{
		gs->range_places = new vector< array2d< unsigned int >* >( range_places->size() );
		for ( unsigned int it = 0; it < range_places->size(); ++it )
			( *gs->range_places )[ it ] = new array2d< unsigned int >( *( *range_places )[ it ] );
	}
	return gs;
};



unsigned long long int game_state::get_hash()
{
	unsigned long long int hash = current_player_id;
	for ( unsigned int x = 0; x < mapa::get_instance()->get_size_x(); ++x )
		for ( unsigned int y = 0; y < mapa::get_instance()->get_size_y(); ++y )
		{
			unit* u = dynamic_cast< unit* >( objects->get( x, y ) );
			if ( u != 0 )
			{
				hash *= 100;
				hash += u->get_x();
				hash *= 100;
				hash += u->get_y();
				hash *= 100;
				hash += u->get_health();
				hash *= 10;
				hash += u->get_player()->get_id();
				hash *= 10;
				hash += u->get_id();
				hash *= 10;
				hash += u->get_nbr();
				hash *= 100;
				int unit_hash = ( u->get_cost_fire() + u->get_cost_move() + u->get_price() + u->get_range() + u->get_shield() + u->get_weapon() ) % 100;
				hash += unit_hash;
			}
		}
	return hash;
};



void game_state::update_all_structures()
{
	if ( reachable_places != 0 )
		delete reachable_places;
	reachable_places = ai_support_computations::map_places_reachable( this );
	if ( estimated_places != 0 )
		delete estimated_places;
	estimated_places = ai_support_computations::map_places_estimate( this );
	if ( dangerous_places != 0 )
		delete dangerous_places;
	dangerous_places = ai_support_computations::map_places_dangerous( this );
	if ( dangerous_places_nobody != 0 )
		delete dangerous_places_nobody;
	dangerous_places_nobody = ai_support_computations::map_places_dangerous_nobody( this );
	if ( attackable_places != 0 )
		delete attackable_places;
	attackable_places = ai_support_computations::map_places_attackable( this );
	if ( range_places != 0 )
	{
		for ( vector< array2d< unsigned int >* >::iterator it = range_places->begin(); it != range_places->end(); ++it )
			delete *it;
		delete range_places;
	}
	range_places = ai_support_computations::map_places_range( this );
	score = ai_support_computations::game_state_estimate( this );
};



void game_state::update_structures()
{
	if ( reachable_places == 0 )
		reachable_places = ai_support_computations::map_places_reachable( this );
	if ( estimated_places == 0 )
		estimated_places = ai_support_computations::map_places_estimate( this );
	if ( dangerous_places != 0 )
		delete dangerous_places;
	dangerous_places = ai_support_computations::map_places_dangerous( this );
	if ( dangerous_places_nobody != 0 )
		delete dangerous_places_nobody;
	dangerous_places_nobody = ai_support_computations::map_places_dangerous_nobody( this );
	if ( attackable_places != 0 )
		delete attackable_places;
	attackable_places = ai_support_computations::map_places_attackable( this );
	if ( range_places != 0 )
	{
		for ( vector< array2d< unsigned int >* >::iterator it = range_places->begin(); it != range_places->end(); ++it )
			delete *it;
		delete range_places;
	}
	range_places = ai_support_computations::map_places_range( this );
	score = ai_support_computations::game_state_estimate( this );
};



void game_state::update_score_structures()
{
	if ( dangerous_places != 0 )
		delete dangerous_places;
	dangerous_places = ai_support_computations::map_places_dangerous( this );
	if ( range_places != 0 )
	{
		for ( vector< array2d< unsigned int >* >::iterator it = range_places->begin(); it != range_places->end(); ++it )
			delete *it;
		delete range_places;
	}
	range_places = ai_support_computations::map_places_range( this );
	score = ai_support_computations::game_state_estimate( this );
};



void game_state::clear_all_structures()
{
	if ( estimated_places != 0 )
		delete estimated_places;
	estimated_places = 0;
	if ( reachable_places != 0 )
		delete reachable_places;
	reachable_places = 0;
	if ( dangerous_places != 0 )
		delete dangerous_places;
	dangerous_places = 0;
	if ( dangerous_places_nobody != 0 )
		delete dangerous_places_nobody;
	dangerous_places_nobody = 0;
	if ( attackable_places != 0 )
		delete attackable_places;
	attackable_places = 0;
	if ( range_places != 0 )
	{
		for ( vector< array2d< unsigned int >* >::iterator it = range_places->begin(); it != range_places->end(); ++it )
			delete *it;
		delete range_places;
	}
	range_places = 0;
};



void game_state::clear_structures()
{
	if ( dangerous_places != 0 )
		delete dangerous_places;
	dangerous_places = 0;
	if ( dangerous_places_nobody != 0 )
		delete dangerous_places_nobody;
	dangerous_places_nobody = 0;
	if ( attackable_places != 0 )
		delete attackable_places;
	attackable_places = 0;
	if ( range_places != 0 )
	{
		for ( vector< array2d< unsigned int >* >::iterator it = range_places->begin(); it != range_places->end(); ++it )
			delete *it;
		delete range_places;
	}
	range_places = 0;
};



void game_state::get_map_structures_from_state( const game_state* state )
{
	if ( estimated_places != 0 )
		delete estimated_places;
	estimated_places = 0;
	if ( state->estimated_places != 0 )
		estimated_places = new array2d< unsigned int >( *state->estimated_places );

	if ( reachable_places != 0 )
		delete reachable_places;
	reachable_places = 0;
	if ( state->reachable_places != 0 )
		reachable_places = new array2d< bool >( *state->reachable_places );
};



double game_state::another_plrs_score( unsigned int aplr )
{
	game_state* temp_state = clone();
	temp_state->current_player_id = aplr;
	temp_state->update_score_structures();
	double score = temp_state->score;
	delete temp_state;

	return score;
};



bool algorithm::init( player* p, const string& s )
{
	owner = p;
	connect( this, SIGNAL( send_command( player*, const string& ) ), game::get_instance(), SLOT( command_received( player*, const string& ) ) );
	return true;
};


player* algorithm::get_owner()
{
	return owner;
};


void algorithm::set_owner( player* p )
{
	owner = p;
};


void algorithm::next_command()
{
	if ( commands.empty() )
	{
		emit send_command( owner, "NXT" );
	}
	else
	{
		string cmd = commands.front();
		commands.pop_front();
		emit send_command( owner, cmd );
	}
};


void algorithm::stop()
{
	commands.clear();
	commands.push_back( "NXT" );
};



ai_algorithms::ai_algorithms( int _x ): x( _x )
{
	reflex_algorithm::register_me();
	replay::register_me();
	search_algorithm::register_me();
	mt_search_algorithm::register_me();
	monte_carlo_algorithm::register_me();
	mt_monte_carlo_algorithm::register_me();
};



ai_algorithms::~ai_algorithms()
{
	for ( map< string, algorithm* >::iterator it = algorithm_list.begin(); it != algorithm_list.end(); ++it )
		delete it->second;
};



void ai_algorithms::register_algorithm( algorithm* newalg )
{
	algorithm_list[ newalg->get_name() ] = newalg;
};



ai_algorithms* ai_algorithms::get_instance()
{
	static ai_algorithms inst(0);
	return &inst;
};



void ai_algorithms::rebuild()
{
};



void ai_algorithms::suspend( unsigned int msecs )
{
	#if defined( WIN32 )
		Sleep( msecs );
	#elif defined( UNIX )
		usleep( msecs * 1000 );
	#else
		#error Unsupported platform
	#endif
};



string ai_algorithms::sec_to_string( unsigned int seconds )
{
	if ( seconds == 0 )
	{
		string null = "0 seconds";
		return null;
	}
	ostringstream sout;
	unsigned int days = seconds / ( 60 * 60 * 24 );
	seconds = seconds % ( 60 * 60 * 24 );
	unsigned int hours = seconds / ( 60 * 60 );
	seconds = seconds % ( 60 * 60 );
	unsigned int minutes = seconds / ( 60 );
	seconds = seconds % ( 60 );
	bool first = true;
	if ( days != 0 )
	{
		if ( !first )
			sout << ", ";
		first = false;
		sout << days << " days";
	}
	if ( hours != 0 )
	{
		if ( !first )
			sout << ", ";
		first = false;
		sout << hours << " hours";
	}
	if ( minutes != 0 )
	{
		if ( !first )
			sout << ", ";
		first = false;
		sout << minutes << " minutes";
	}
	if ( seconds != 0 )
	{
		if ( !first )
			sout << ", ";
		first = false;
		sout << seconds << " seconds";
	}
	return sout.str();
};